package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/8 17:01
 * https://leetcode.cn/problems/reconstruct-itinerary/
 */
public class Title332II {

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> edge : tickets) {
            graph.computeIfAbsent(edge.get(0), k -> new PriorityQueue<>()).offer(edge.get(1));
        }
        List<String> paths = new ArrayList<>();
        dfs(graph, paths, "JFK");
        return paths;
    }

    private void dfs(Map<String, PriorityQueue<String>> graph, List<String> paths, String city) {
        PriorityQueue<String> priorityQueue = graph.getOrDefault(city, new PriorityQueue<>());
        while (!priorityQueue.isEmpty()) {
            dfs(graph, paths, priorityQueue.poll());
        }
        paths.add(0, city);
    }

    public static void main(String[] args) {


    }
}
